package 动态规划;
/**
 * 这个题 主要 学习 一下这个思想吧
 * （这个题的描述 跟 shit 一样）
 * 并稍微的改变一下 这个题
 * 
 * 每一阶 楼梯 都对应着 一个 cost[i] 
 * 到达相应的 楼梯 就需要 花费 cost[i]
 * 每一次的 选择 choice [] = {1,2,.....}  (解释: 就是一次 可以 跨一步 或者 跨 两步 甚至 可以 跨更多步 根据 题目中所给的 choice 的 值 )
 * 问 爬到 给定的  steps 花费最小 多少
 */
public class leetcode最小花费爬楼梯 {
	
	
	/**
	 *这题 就是个傻逼 题
	 */
	
	public static void main(String []args) {
//		int costs[] = {3,12,5,6,7};
//		int ans = function(costs.length,costs);
//		System.out.println(ans);
		
		int choice [] = {1,2};
		int steps = 5;
		System.out.println(compare(steps)+" && "+function(steps,choice,0));
		
		
	}
	
	
	
	/**
	 * 这个 问题 当中最核心的 一个 问题 是 
	 * 这个 steps 这个参数  表示的 意义 是什么
	 * 两种解释:
	 * 1. 当前 爬到 第几层了
	 * 
	 * 2. 还剩余 几 steps 要爬 
	 * 
	 * 上面 两种解释 都可以 
	 * 但是传入的参数是不一样的 
	 * 1. 传入的 起始  数据 是  0 , 1 这些开始的 数据
	 * 
	 * 2.这种 思想的 话 传入的参数就是  arr.length 或者 arr.length - 1
	 * 
	 *   这两种 思考的 方式  一个是 从头 到尾
	 *   一个是 从尾 到头
	 */
		
	
	public static int function(int steps,int []costs) {
		if(steps <= 0)
			return 0;
//		int ans = 0;
//		 int cost1 = 0;
//		 int cost2 = 0;
		 /**
		 cost1 +=function(steps - 1,costs) + costs[steps]; 
		 cost2  += function(steps - 2,costs) + costs[steps];
		 
		 return Math.min(cost1, cost2);
		 对上面的 代码进行小小的改进 
		 Math.min(function(steps - 1,costs) + costs[steps], function(steps - 2,costs) + costs[setps])
		 
		 两边同时加上  costs[steps]  ,调用min 函数的 时候 相当于 没有 添加 呗
		 
		 所以最后 再把 costs[steps] 加到 返回结果上面 也是一样的
		  */
		
		 	return Math.min(function(steps - 1,costs), function(steps - 2,costs)) + costs[steps - 1];
		 
	}

	/**
	 * 使用 二叉树 (递归 形成的 模板)
	 * 选或者 不选
	 */
	
	public static int function(int steps,int choice[],int index) {
		if(index > 1)
			return 0;
		if(steps == 1 )
			return 1;
		
		if(steps == 2)
			return 2;
//		if(steps <= 0)
//			return 1;
		// 选
		int res1 = function(steps - choice[index],choice,index);
		
		// 不选
		int res2 = function(steps,choice,index + 1);
		return res1 + res2;
		//return function(steps - choice[index],choice,index) + function(steps,choice,index + 1);
	}
	
	public static int function(int steps) {
		if(steps == 1 )
			return 1;
		
		if(steps == 2)
			return 2;
//		if(steps <= 0)
//			return 1;
		// 选
		int res1 = function(steps - 1);
		
		// 不选
		int res2 = function(steps);
		return res1 + res2;
		//return function(steps - choice[index],choice,index) + function(steps,choice,index + 1);
	}
	
	
	
	
	public static int compare(int steps) {
		if(steps == 1 )
			return 1;
		
		if(steps ==2)
			return 2;
//		if(steps <= 0)
//			return 1;
		return compare(steps - 1) + compare(steps -2);
	}
	
	
}
